public class Solution1292 {
    public int maxSideLength(int[][] mat, int threshold) {
        int[][] sum=new int[mat.length+1][mat[0].length+1];
        for (int i=0;i<mat.length;i++){
            for (int j=0;j<mat[0].length;j++){
                sum[i+1][j+1]=sum[i][j+1]+sum[i+1][j]+mat[i][j]-sum[i][j];
            }
        }
        int l=1,r=Math.min(mat.length,mat[0].length),ans=0;
        while (l<=r){
            int mid=(l+r)/2;
            int min=Integer.MAX_VALUE;
            for (int i=0;i<mat.length;i++){
                for (int j=0;j<mat[0].length;j++){
                    if (i-mid+1>=0 && j-mid+1>=0){
                        min=Math.min(min,sum[i+1][j+1]-sum[i+1][j-mid+1]-sum[i-mid+1][j+1]+sum[i-mid+1][j-mid+1]);
                    }
                }
            }
            if (min<=threshold){
                ans=mid;
                l=mid+1;
            }else {
                r=mid-1;
            }
        }
        return ans;
    }

    public static void main(String[] args) {
        System.out.println(new Solution1292().maxSideLength(new int[][]{{1,1,3,2,4,3,2},{1,1,3,2,4,3,2},{1,1,3,2,4,3,2}},4));
    }
}
